package com.sgg.datastructure.recursion;

public class 迷宫 {
    /**
     * @param i 行
     * @param j 列
     */
    public static int[][] init(int i, int j) {
        int[][] map = new int[i][j];
        //外面一圈是墙
        for (int x = 0; x < 7; x++) {
            map[0][x] = 1;
            map[7][x] = 1;
        }
        for (int y = 1; y < 7; y++) {
            map[y][0] = 1;
            map[y][6] = 1;
        }
        return map;
    }

    public static void show(int[][] map) {
        for (int[] ints : map) {
            for (int i : ints) {
                System.out.printf("%d\t", i);
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        int[][] map = init(8, 7);
        map[3][1] = 1;
        map[3][2] = 1;
        show(map);
        System.out.println(setWay(map,1,1,6,5));
        show(map);

    }

    /**
     * 利用递归解决迷宫问题
     * 思路,0代表没走过,1代表墙,2代表走成功了,3代表不成功
     * 先下,然后右,然后走上,然后左
     * @param map
     * @param iy
     * @param ix
     * @param resultY
     * @param resultX
     * @return
     */
    public static boolean setWay(int[][] map, int iy, int ix, int resultY, int resultX) {
        if (map[resultY][resultX] == 2) {
            return true;
        }
        if (map[iy][ix]==0) {
            map[iy][ix] = 2;
            if (setWay(map, iy+1, ix ,resultY,resultX)) {//下
                return true;
            }else if(setWay(map, iy, ix+1 ,resultY,resultX)){//右
                return true;
            } else if (setWay(map, iy-1, ix, resultY, resultX)) {//上
                return true;
            }else if (setWay(map, iy, ix-1, resultY, resultX)) {//左
                return true;
            }else {
                map[iy][ix] = 3;
                return false;
            }
        }else {
            return false;
        }
    }
}
